package com.gao.alg;

import java.util.Arrays;

/**
 * @author gao
 * @date 2023/12/07 09:33:30
 */
public class MergeSort {
    public static void mergeSort(int[] arr) {
        int[] tmpArr = new int[arr.length];
        mergeSort(arr, tmpArr, 0, arr.length - 1);
    }

    public static void mergeSort(int[] arr, int[] tmpArr, int start, int end) {
        if (start >= end) {
            return;
        }

        int mid = (start + end) / 2;
        mergeSort(arr, tmpArr, start, mid);
        mergeSort(arr, tmpArr, mid + 1, end);

        merge(arr, tmpArr, start, mid, end);
    }

    private static void merge(int[] arr, int[] tmpArr, int start, int mid, int end) {
        int i = start;
        int i2 = mid + 1;
        int i3 = start;

        while (i <= mid && i2 <= end) {
            if (arr[i] < arr[i2]) {
                tmpArr[i3++] = arr[i++];
            } else {
                tmpArr[i3++] = arr[i2++];
            }
        }

        while (i <= mid) {
            tmpArr[i3++] = arr[i++];
        }

        while (i2 <= end) {
            tmpArr[i3++] = arr[i2++];
        }

        for (int j = start; j <= end; j++) {
            arr[j] = tmpArr[j];
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 7, 5, 4, 6, 8, 10, 9, 2};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}
